package hot100.logos61To70;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author logos
 * date 2025/7/17 12:12
 * @version v1.0
 * @Package hot100.logos61To70
 */
public class logos69 {

    /**
     * 69. 有效的括号
     * https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        private static final Map<Character, Character> map = new HashMap<>();

        static {
            map.put('{', '}');
            map.put('[', ']');
            map.put('(', ')');
        }

        public boolean isValid(String s) {
            if (s.length() > 0 && !map.containsKey(s.charAt(0))) {
                return false;
            }
            LinkedList<Character> st = new LinkedList<>();
            st.addLast('.');
            for (Character c : s.toCharArray()) {
                if (map.containsKey(c)) {
                    st.addLast(c);
                } else if (!map.get(st.removeLast()).equals(c)) {
                    return false;
                }
            }
            return st.size() == 1;
        }
    }
}
